In the paper we consider the problem of scheduling $n$ identical jobs on 4uniform machines with speeds $s_1 \geq s_2 \geq s_3 \geq s_4,$ respectively.Our aim is to find a schedule with a minimum possible length. We assume thatjobs are subject to some kind of mutual exclusion constraints modeled by abipartite incompatibility graph of degree $\Delta$, where two incompatible jobscannot be processed on the same machine. We show that the problem is NP-hardeven if $s_1=s_2=s_3$. If, however, $\Delta \leq 4$ and $s_1 \geq 12 s_2$,$s_2=s_3=s_4$, then the problem can be solved to optimality in time$O(n^{1.5})$. The same algorithm returns a solution of value at most 2 timesoptimal provided that $s_1 \geq 2s_2$. Finally, we study the case $s_1 \geq s_2\geq s_3=s_4$ and give an $O(n^{1.5})$-time $32/15$-approximation algorithm inall such situations.
展开▼
